Back to course home
0% completed
Vote For New Content
Google Hard
Shortest Subarray with Sum at Least K (hard)
Solution: Shortest Subarray with Sum at Least K
Reverse Pairs (hard)
Solution: Reverse Pairs
Nth Magical Number (hard)
Solution: Nth Magical Number
Candy (hard)
Solution: Candy
Arithmetic Slices II - Subsequence (hard)
Solution: Arithmetic Slices II - Subsequence
Burst Balloons (hard)
Solution: Burst Balloons
Sum of Distances in Tree (hard)
Solution: Sum of Distances in Tree
Maximum Score of a Good Subarray (hard)
Solution: Maximum Score of a Good Subarray
Trapping Rain Water (hard)
Solution: Trapping Rain Water
First Missing Positive (hard)
Solution: First Missing Positive
Furthest Building You Can Reach (medium)
Problem Statement
You are given an array of integers heights, where heights[i] is the height of the ith building, integer bricks, and integer ladders.
You start traveling from the first building and move to the next building by either using bricks or ladders.
Each time you encounter a building taller than the one you're currently on, you have two options:
- climb up using a
fixed amountof bricks for each unit of height difference - Or, utilize a
ladderto bypass the height difference entirely
Return the index (0-indexed) of the furthest building you can reach if you use the given ladders and bricks optimally.
Examples
Example 1:
- Input:
heights = [4,12,2,7,3,18,20,3,19], bricks = 10, ladders = 2 - Expected Output:
7 - Justification:
- Move from building 0 to 1 using a ladder.
- Move from building 1 to 2 without using any resources.
- Move from building 2 to 3 using 5 bricks.
- Move from building 3 to 4 without using any resources.
- Move from building 4 to 5 using a ladder.
- Move from building 5 to 6 using 2 bricks.
- Move from building 3 to 4 without using any resources.
Example 2:
- Input:
heights = [1,5,1,2,3,4,10000], bricks = 4, ladders = 1 - Expected Output:
5 - Justification: Use the ladder for the large jump from 0 to 1. Use bricks for smaller climbs from 1 to 2, 2 to 3, 3 to 4, and 4 to 5. This strategy gets you to the 5th building before running out of resources.
Example 3:
- Input:
heights = [5,1,1,1,1,1,1,1,1,1,20], bricks = 10, ladders = 1 - Expected Output:
10 - Justification: Use the ladder for the last large climb from 9 to 10 buildings. Bricks can be used for one of the single-unit climbs if necessary, allowing you to reach the last building.
Try it yourself
Try solving this question here:
Java
Saved to Cloud
. . . .
Solution: 4Sum II
Solution: Furthest Building You Can Reach
Mark as Completed
On this page
Problem Statement
Examples
Try it yourself